package 剑指专题.搜索算法;


/*
 * Author：江松
 * Date：2023/3/29 13:29
 *
 字符串的排列：
 1，DFS全排列问题,其中需要利用集合去重
 2，剪枝，
   if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
                //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
                continue;
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class Main5 {

    private boolean vis[];
    private int len;
    private String s;
    Set<String> tmp=new HashSet<>();

    public void dfs(int id,StringBuilder sb){
        if(id==len){
            tmp.add(sb.toString());
            return;
        }
        for(int i=0;i<len;++i){
            if(!vis[i]){
                vis[i]=true;
                sb.append(s.charAt(i));
                dfs(id+1,sb);
                //sb.delete(id,id+1);//左闭右开
                sb.deleteCharAt(id);
                vis[i]=false;
            }
        }
    }


    public ArrayList<String> Permutation(String str) {
        this.s=str;
        this.len=s.length();
        this.vis=new boolean[len+1];
        dfs(0,new StringBuilder());
        return new ArrayList<>(tmp);
    }
}
